import java.util.ArrayList;
import java.util.List;

public class Solution {
    //判断两颗子树是否是同一颗树(判断树里的元素是否相同)
    public boolean IsSameTree(TreeNode p,TreeNode q){
        //根为空
        if(p==null&&q==null){
            return true;
        }
        if(p==null||q==null){
            return false;
        }

        return p.val==q.val&&IsSameTree(p.left,q.left)&&IsSameTree(p.right,q.right);
            /*
             boolean res=IsSameTree( p.left, target.left);
            if(res!=true){
                return false ;
            }
            return IsSameTree( root.right, target.right);
            */
    }
    //用List判断二叉树种是否有找树中是否包含某元素
    public List<TreeNode> preOrder(TreeNode root){
        List<TreeNode> ans = new ArrayList<>();
        if(root==null){
            return ans;
        }
        ans.add(root);
        ans.addAll(preOrder(root.left));
        ans.addAll(preOrder(root.right));
        return ans;

    }
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(subRoot==null){
            return true;
        }
        List<TreeNode> list = preOrder(root);
        //遍历每一个结点
        for(TreeNode node:list){
            if(node.val==subRoot.val){
                if(IsSameTree(node,subRoot))
                {
                    return true;
                }
            }
        }
        return false;
    }
}
